const { TreeNode } = require('../common')

/* 递归实现 */
var preorderTraversal = function (root) {
  if (root === null) return []
  let ans = [root.val]
  if (root.left) ans = ans.concat(...preorderTraversal(root.left))
  if (root.right) ans = ans.concat(...preorderTraversal(root.right))
  return ans
}


/* 迭代实现 */
var preorderTraversal = function (root) {
  let ans = []
  if (root) {
    let stack = [root]
    while (stack.length > 0) {
      let tmp = stack.pop()
      ans.push(tmp.val)
      if (tmp.right) stack.push(tmp.right)
      if (tmp.left) stack.push(tmp.left)
    }
  }

  return ans
}
let root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3, null, null), null))

preorderTraversal(root)